package src.greed;

public class no45 {//跳跃游戏2

    /**
     * 需要统计两个覆盖范围，当前这一步的最大覆盖cover 和下一步最大覆盖next
     */
    public int jump(int[] nums) {
        if (nums.length == 1 && nums[0] >= 0) return 0;

        int cover = 0;//当前覆盖范围
        int count = 0;//步数
        int next = 0;//下一步的范围

        // i 只能在覆盖范围内移动
        for (int i = 0; i < nums.length; i++) {
            next = Math.max(i + nums[i], next);  //每次更新cover，选现在能达到的最大范围
            //注意：看的是覆盖范围能到哪里，不是看步数谁最大
            if (i == cover) {

                count++;
                cover = next;
                if (next >= nums.length - 1) break;

            }
        }
        return count;
    }

    public int jump2(int[] nums) {
        if (nums == null || nums.length == 0 || nums.length == 1) return 0;
        int count = 0, cover = 0, next = 0;
        for (int i = 0; i < nums.length; i++) {
            //在可覆盖区域内更新下一步能达到的最大区域
            next = Math.max(i + nums[i], next);
            //如果下一步已经达到终点了，步数+1后退出
            if (next >= nums.length - 1) {
                count++;
                break;
            }
            // i 遍历到当前这步的最大范围，就更新当前范围的起始点
            if (i == cover) {
                cover = next;
                count++;
            }
        }
        return count;
    }
}
